package ChainTable;

public class SingleLinkedListWithHead {
    //单链表建立虚拟头节点，解决头节点处理麻烦问题
    private int size;
    private Node dummyHead = new Node(-100);

    /**
     * 根据索引增加节点
     *
     * @param index
     * @param val
     */
    public void addIndex(int index, int val) {
        if (index < 0 || index > size) {
            System.out.println("add index illegal!");
            return;
        }
        Node node = new Node(val);
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        node.next = prev.next;
        prev.next = node;
        size++;
    }

    public void addFirst(int val) {
        addIndex(0, val);
    }

    public void addLast(int val) {
        addIndex(size, val);
    }

    /**
     * 根据索引查找结点值
     *
     * @param index
     * @return 输出节点值
     */
    public int getVal(int index) {
        if (rangeIndex(index)) {
            Node prev = dummyHead;
            for (int i = 0; i <= index; i++) {
                prev = prev.next;
            }
            return prev.val;
        } else {
            System.out.println("get index illegal!");
            return -1;
        }
    }

    /**
     * 判断链表中是否存在该值
     *
     * @param val
     * @return 存在true/不存在false
     */
    public boolean contains(int val) {
        for (Node prev = dummyHead; prev != null; prev = prev.next) {
            if (prev.val == val) {
                return true;
            }
        }
        return false;
    }

    /**
     * 根据索引修改节点存储的值
     *
     * @param index
     * @param newVal
     * @return 输出旧的节点值
     */
    public int setVal(int index, int newVal) {
        if (rangeIndex(index)) {
            Node prev = dummyHead;
            for (int i = 0; i <= index; i++) {
                prev = prev.next;
            }
            int oldVal = prev.val;
            prev.val = newVal;
            return oldVal;
        } else {
            System.out.println("set index illegal!");
            return -1;
        }
    }

    /**
     * 根据索引删除数据节点
     *
     * @param index
     */
    public void removeIndex(int index) {
        if (rangeIndex(index)) {
            Node prev = dummyHead;
            for (int i = 0; i < index; i++) {
                prev = prev.next;
            }
            Node cur = prev.next;
            prev.next = cur.next;
            cur.next = null;
            size--;
        } else {
            System.out.println("remove index illegal!");
        }
    }

    public void removeFirst() {
        removeIndex(0);
    }

    public void removeLast() {
        removeIndex(size - 1);
    }

    /**
     * 删除链表中第一个值为val的节点
     * @param val
     */
    public void removeValOnce(int val) {
        for (Node prev=dummyHead;prev.next!=null;prev=prev.next){
            if (prev.next.val==val){
                Node cur = prev.next;
                prev.next=cur.next;
                cur.next=null;
                size--;
                break;
            }
        }
    }

    /**
     * 删除链表中所有值为val的节点
     * @param val
     */
    public void removeValAll(int val){
        Node prev = dummyHead;
        while (prev.next!=null){
            if (prev.next.val==val){
                Node cur = prev.next;
                prev.next=cur.next;
                cur.next=null;
                size--;
            }else{
                prev=prev.next;
            }
        }
    }

    @Override
    public String toString() {
        String ret = "";
        Node prev = dummyHead.next;
        while (prev != null) {
            ret += prev.val + "->";
            prev = prev.next;
        }
        ret += "Null";
        return ret;
    }

    private boolean rangeIndex(int index) {
        if (index < 0 || index >= size)
            return false;
        return true;
    }
}
